package com.LeeCode;

import java.util.Arrays;

/**
 * 找出第 K 小的数对距离
 */

public class Code719 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1};
        int k = 2;
        System.out.println(new Code719().smallestDistancePair(nums, k));
    }

    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int left = -1, right = nums[nums.length - 1] - nums[0];
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(nums, mid, k))
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    // 判断距离差小于m的数据对是否至少有k对
    private boolean check(int[] nums, int m, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[j] - nums[i]) > m) break;
                count++;
                if (count >= k)
                    return true;
            }
        }
        return false;
    }
}
